package com.yx.study.leet.questionList.questions;

import org.junit.Test;

/**
 * 29. 两数相除
 * 给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
 * https://leetcode.cn/problems/divide-two-integers/
 */
public class Solution29 {
    public int divide(int dividend, int divisor) {
        dividend = dividend > 0 ? dividend : add(~dividend , 1); // 负数取反+1
        divisor = divisor > 0 ? divisor : add(~divisor ,1);
        int quotient = 0;// 商
        for(int i = 31; i >= 0; i--) {
            //比较dividend是否大于divisor的(1<<i)次方，不要将dividend与(divisor<<i)比较，而是用(dividend>>i)与divisor比较，
            //效果一样，但是可以避免因(divisor<<i)操作可能导致的溢出，如果溢出则会可能dividend本身小于divisor，但是溢出导致dividend大于divisor
            if((dividend >> i) >= divisor) {
                quotient = add(quotient, 1 << i);
                dividend = substract(dividend, divisor << i);
            }
        }
        // 确定商的符号
        if((dividend ^ divisor) < 0){
            // 如果除数和被除数异号，则商为负数
            quotient = add(~quotient, 1);
        }
        return quotient;// 返回商
    }

    public int add(int a, int b) {
        while (b != 0) {
            int temp = a ^ b; //计算出相对应的位置相加后的结果
            b = (a & b) << 1; //计算出想对应的位置的进位，然后左移一位
            a = temp;
        }
        return a;
    }

    public int substract(int num1, int num2){
        int subtractor = add(~num2, 1);// 先求减数的补码（取反加一）
        int result = add(num1, subtractor); // add()即上述加法运算　　
        return result ;
    }

    @Test
    public void test(){
        System.out.println(divide(10, -3));
    }
}
